package DataStructure.graph;

import DataStructure.linear.Queue;

public class Digraph {
    private final int V;
    private int E;
    private Queue<Integer>[] adj;//邻接表

    public Digraph(int v){
        this.V=v;
        this.E=0;
        this.adj=new Queue[v];
        for (int i = 0; i < adj.length; i++) {
            adj[i]=new Queue<Integer>();
        }
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    //添加边v->w
    public void addEdge(int v,int w){
        //只需要让顶点w出现在顶点v的邻接表中，顶点v的邻接表存储的相邻顶点的含义是v->其他顶点
        adj[v].enqueue(w);
        E++;
    }

    //获取v指出的边所连接的所有顶点
    public Queue<Integer> adj(int v){
        return adj[v];
    }

    //获取反向图
    public Digraph reverse(){

        Digraph r = new Digraph(V);
        for (int v = 0; v < V; v++) {
            //获取该顶点v指出的所有边
            for (Integer w : adj[v]) {//原图中表示的是顶点v指向w的边
                r.addEdge(w,v);
            }
        }
        return r;
    }
}
